package org.usmile.algorithms.leetcode.simple;

import java.util.ArrayList;
import java.util.List;

/**
 * 119. 杨辉三角 II
 *
 * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * 示例 1:
 *
 * 输入: rowIndex = 3
 * 输出: [1,3,3,1]
 * 示例 2:
 *
 * 输入: rowIndex = 0
 * 输出: [1]
 * 示例 3:
 *
 * 输入: rowIndex = 1
 * 输出: [1,1]
 *
 * 提示:
 *
 * 0 <= rowIndex <= 33
 */
public class _0119 {
}

class _0119_Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> oneRow = new ArrayList<>();
        oneRow.add(1);
        for (int row = 1; row <= rowIndex; row++) {
            oneRow.add(0);
            for (int col = row; col > 0; col--) {
                oneRow.set(col, oneRow.get(col - 1) + oneRow.get(col));
            }
        }

        return oneRow;
    }
}


class _0119_Solution1 {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<>();
        pre.add(1);
        for (int row = 1; row <= rowIndex; row++) {
            List<Integer> curr = new ArrayList<>();
            curr.add(1);
            if (row > 0) {
                for (int i = 1; i < row; i++) {
                    curr.add(pre.get(i - 1) + pre.get(i));
                }
                curr.add(1);
            }
            pre = curr;
        }

        return pre;
    }
}
